package com.dragon.datastructure.hash;

/**
 * 得到一个字符串第一个不重复的字符的索引，如果没有，则返回-1
 * 假定: 该字符串都是小写
 *
 * @author dragon
 * @since 2019/12/27
 */
public class UnqiueChar {

    public static void main(String[] args) {
        String str = "abcabdf";
        System.out.println(getUniqueCharIndex(str));
    }

    /**
     * 在这个程序中，哈希表就是frequency，它存储的是str中每一个字符出现的频率
     * 而哈希函数就是f(ch) = ch - 'a'； 对于每一个键ch，通过哈希函数 ch - 'a' 来求的在哈希表中的索引
     * 键 --》 哈希函数 ---》 索引
     * <p>
     * 而"键"通过哈希函数得到的"索引"分布的越均匀越好
     * <p>
     * 哈希函数的设计:
     * 整形:
     * 小范围正整数直接使用
     * 小范围内负整数进行偏移 -100 ～ 100 ==》 0 ～ 200
     * <p>
     * 大整数
     * 身份证号 420821199211183458
     * 取模: 比如取后四位。等同于 mod 10000
     * 一个简单的解决办法: 模一个素数
     * <p>
     * 字符串 转成整型处理
     * code = c * 26^3 + o * 26 ^ 2 + d * 26 ^ 1 + e * 26 ^0
     * code = c * B^3 + o * B ^ 2 + d * B ^ 1 + e * B ^0
     * Hash(code) = (c * B^3 + o * B ^ 2 + d * B ^ 1 + e * B ^0) % M
     * Hash(code) = ((((c * B) + o) * B + d) * B + e) % M
     * Hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M
     * <p>
     * <p>
     * int hash = 0;
     * for(int i = 0; i < s.length(); i++) {
     * hash = (hash * B + s.charAt(i)) % M
     * }
     * <p>
     * 复合类型
     * Date : year, month, day
     * hashCode(date) = ((date.year * B) + date.month) * B + date.day
     * <p>
     * 转换成整型处理并不是唯一的方法！
     * 原则
     * 1. 一致性: 如果 a== b, 则hash(a) == hash(b)
     * 2. 高效性: 计算高效简便
     * 3. 均匀性: 哈希值均匀分布
     *
     * @param str
     * @return
     */
    public static int getUniqueCharIndex(String str) {
        if (str == null) {
            return -1;
        }
        // 定义一个26个长度的数组,存储字符串每一个字符所对应的频率
        int[] frequency = new int[26];
        for (int i = 0; i < str.length(); i++) {
            frequency[str.charAt(i) - 'a']++;
        }
        for (int i = 0; i < str.length(); i++) {
            if (frequency[str.charAt(i) - 'a'] == 1) {
                return i;
            }
        }

        return -1;

    }
}
